package pri.zjy.linkedList;

import pri.zjy.linkedList.model.ListNode;

import java.util.HashSet;
import java.util.Set;

/**
 * @author zhangjy
 * @description 相交链表
 * @date 2025/5/7 15:39
 */
public class GetIntersectionNode_160 {

    /**
     * 官解：双指针
     */
    public ListNode getIntersectionNode4(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode pA = headA, pB = headB;
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }

    /**
     * 参考dmsxl：双指针
     * <p>
     * 分析：
     * 1.如果两个链表相交于节点C，表明节点C及其之后的链表一致，也就是说节点C及后面，两个链表的长度相同；
     * 1.1.那么，只需考虑前面部分（节点C前面的链表），若两个链表前面部分的长度也相同，两链表同时从头往后遍历（两链表向右对齐，然后遍历比较）；
     * 由于步长相同、长度相同，那么一定能同时找到节点C，即headA.next = headB.next出现。
     * 1.2.为什么若相交，向右对齐遍历一定能找到相交节点？
     * ——因为相交节点后面部分，两链表相同，只有前面部分有差别（可能一长一短，也可能长度相同）；
     * 向右对齐后，相当于逻辑上两链表长度相同，都从头开始遍历；这时，如果有相交节点，那边一定会找到。
     * 2.相反，若对齐遍历后，仍然找不到相等的指针，表明两个链表没有相交。
     *
     * <p>
     * T(n) = 0(n + m)；其中 m 和 n 是分别是链表 headA 和 headB 的长度。
     * S(n) = O(1)
     */
    public ListNode getIntersectionNode3(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;

        // 统计两链表长度
        int lengthA = getLength3(headA);
        int lengthB = getLength3(headB);
        int diff = lengthA - lengthB;
        // 对齐两个链表（curA、curB在同一起点）
        ListNode curA = headA, curB = headB;
        while (diff != 0) {
            if (diff > 0) {
                curA = curA.next;
                diff--;
            } else {
                curB = curB.next;
                diff++;
            }
        }

        // 找相交链表
        while (curA != null || curB != null) {
            if (curA == curB) return curA;
            curA = curA.next;
            curB = curB.next;
        }

        return null;
    }

    public int getLength3(ListNode node) {
        int length = 0;
        while (node != null) {
            length++;
            node = node.next;
        }
        return length;
    }

    /**
     * 个人：哈希表
     * <p>
     * T(n) = 0(n + m)
     * S(n) = O(n)
     */
    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;

        Set<ListNode> setA = new HashSet<>();
        ListNode curA = headA;
        while (curA != null) {
            setA.add(curA);
            curA = curA.next;
        }

        ListNode curB = headB;
        while (curB != null) {
            if (setA.contains(curB)) return curB;
            curB = curB.next;
        }
        return null;
    }

    /**
     * 个人：暴力解法-双重循环
     * <p>
     * T(n) = O(n*m)；其中n、m分别是headA和headB的长度。
     * S(n) = O(1)
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curA = headA;
        while (curA != null) {
            ListNode curB = headB;
            while (curB != null) {
                if (curA == curB) return curA;
                curB = curB.next;
            }
            curA = curA.next;
        }
        return null;
    }

}
